/*
 * The Stupid Turing Machine Emulator.
 *
 * Licensed under GNU LGPL version 3 license.
 * Copyright (C) 2012-2013, Andrew Tselischev.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <assert.h>
#include <ctype.h>

#define IN_BUF 1024
#define ST_NAME_LEN 128
#define STR_FINAL_STATE    "FINAL STATE"
#define STR_HEAD_POSITION  "HEAD POSITION"
#define STR_TAPE           "TAPE"
#define STR_VERBOSE        "VERBOSE"
#define STR_CHANGES        "CHANGES"
#define STR_TOLLIM         "TOLERANCE"

#define NULLCHR '~' /* use tilde as the null character */

/*
 * Turing Machine emulator
 *
 * Input:
 *  <list of commands (1 per line)>
 *  FINAL STATE
 *  <state_id>
 *  HEAD POSITION
 *  <index offset>
 *  TAPE
 *  <symbols>
 *
 * Where
 * command ::= <state_id> <symbol> -> <state_id> <symbol> ( 'L' | 'R' | '.' )
 * state_id ::= number between -2^31 and 2^31-1
 */

/*
 * TODO:
 *  - work out a sensible input and output format
 *  - implement sane execution verbosity switch
 *  - implement autodetection of the final state
 */

struct cell {
	char symbol;
	struct cell *left;
	struct cell *right;
};

/*
 * This is how it works:
 * We look at what's in the current cell.
 * If it matches 'state.symbol' then we put 'state.update_symbol'
 * in the current cell, modify head according to 'state.move' and switch to
 * 'state.next_state_id' state.
 */
struct state {
	int state_id;
	int next_state_id;
	char *state_name;
	char *next_state_name;
	char symbol;
	char update_symbol;
	char move;
	bool is_final;
};

struct statepool {
	struct state *states;
	size_t n;
	size_t size;
};

extern int launch_tm(struct statepool *, struct cell *, bool, bool, const int);
int statecmp(const void *, const void *);
static int tape_cleanup(struct cell *);
static struct cell *tape_init(char *, const int);
static struct cell *tape_insert_left(struct cell * const);
static struct cell *tape_insert_right(struct cell * const);
static struct statepool *statepool_init(void);
static void mark_final_state(struct statepool *, int);
static void statepool_append_copy(struct statepool *, struct state *);
static int statepool_cleanup(struct statepool *);
static void *my_malloc(size_t);
static void *my_realloc(void *, size_t);

static void *
my_realloc(void *ptr, size_t newsize)
{
	void *ret;
	if ((ret = realloc(ptr, newsize)) == NULL) {
		fprintf(stderr,
			"Failed to realloc %lu bytes\n"
			"Exiting\n", newsize);
		exit(EXIT_FAILURE);
	}
	return (ret);
}

static void *
my_malloc(size_t size)
{
	void *p;
	if ((p = malloc(size)) == NULL) {
		fprintf(stderr,	"Failed to allocate %lu bytes\n"
			"Exiting\n", size);
		exit(EXIT_FAILURE);
	}
	return (p);
}

static struct statepool *
statepool_init(void)
{
	struct statepool *v;

	v = my_malloc(sizeof(struct statepool));
	v->size = 8;
	v->n    = 0;
	v->states = my_malloc(v->size * sizeof(struct state));
	return (v);
}

static void
statepool_append_copy(struct statepool *v, struct state *data)
{
	if (v->n >= v->size) {
		v->size *= 2;
		v->states = my_realloc(v->states,
				v->size * sizeof *data);
	}
	v->states[v->n++] = *data;
}

static void
statepool_sort(struct statepool *v, int (*cmp)(const void *, const void *))
{
	if (v == NULL || cmp == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything\n",
				__func__);
		return;
	}

	qsort(v->states, v->n, sizeof v->states[0], cmp);
}

static int
statepool_cleanup(struct statepool *v)
{
	if (v) {
		free(v->states);
		v->states = NULL;
	}
	free(v);
	return (0);
}

extern int
statecmp(const void *p1, const void *p2)
{
	struct state *s1, *s2;

	assert(p1 != NULL && p2 != NULL);

	s1 = (struct state *) p1;
	s2 = (struct state *) p2;

	if (s1->state_id == s2->state_id)
		return (s1->symbol - s2->symbol);
	return (s1->state_id - s2->state_id);
}

static void
mark_final_state(struct statepool *v, int fin_st_id)
{
	int i = 0;
	while (i < v->n) {
		if (v->states[i].state_id == fin_st_id)
			v->states[i].is_final = true;
		i++;
	}
}

static struct state *
find_rule(struct statepool *v, int state_id, char symbol)
{
	int i = 0;
	while (i < v->n) {
		if (v->states[i].state_id == state_id &&
				v->states[i].symbol == symbol)
			return (v->states + i);
		i++;
	}
	return (NULL);
}

static int
statenames_link(char ***_reg, struct state *st, char *state_name,
		char *next_state_name, struct statepool *stpool)
{
	int i = 0;
	char **reg;

	assert(_reg != NULL && *_reg != NULL);
	assert(st != NULL);
	assert(next_state_name != NULL);
	assert(stpool != NULL);

	reg = *_reg; /* because 'reg' may change after calling realloc */

	i = 0;
	while (reg[i]) {
		if (!strcmp(state_name, reg[i]))
			break;
		i++;
	}
	if (reg[i] == NULL) {
		reg = my_realloc(reg, (i + 2) * sizeof *reg);
		*_reg = reg;
		reg[i + 1] = NULL;
		reg[i] = my_malloc(strlen(state_name) + 1UL);
		strncpy(reg[i], state_name, strlen(state_name) + 1UL);
	}
	st->state_name = reg[i];
	st->state_id = i;

	i = 0;
	while (reg[i]) {
		if (!strcmp(next_state_name, reg[i]))
			break;
		i++;
	}
	if (reg[i] == NULL) {
		reg = my_realloc(reg, (i + 2) * sizeof *reg);
		*_reg = reg;
		reg[i + 1] = NULL;
		reg[i] = my_malloc(strlen(next_state_name) + 1UL);
		strncpy(reg[i], next_state_name, strlen(next_state_name) + 1UL);
	}
	st->next_state_name = reg[i];
	st->next_state_id = i;

	return (0);
}

static int
st_name_register__free(char ***_reg)
{
	char **reg;

	assert(_reg != NULL && *_reg != NULL);

	reg = *_reg;
	while (*reg) {
		(*reg)[0] = '\0';
		free(*reg);
		*reg = NULL;
		++reg;
		/* is this overcomplicated? */
	}
	free(*_reg);
	*_reg = NULL;

	return (0);
}

/*
 * These two functions insert new cells to the left or right of the 'current'
 * cell and initialize them with defined null characted (tilde by default).
 *
 * Return pointer to newly created cell.
 */
static struct cell *
tape_insert_left(struct cell * const current)
{
	struct cell *prev;

	prev = current->left;
	current->left = my_malloc(sizeof(struct cell));
	current->left->symbol = NULLCHR;
	current->left->left   = prev;
	current->left->right  = current;
	if (prev)
		prev->right = current->left;

	return (current->left);
}

static struct cell *
tape_insert_right(struct cell * const current)
{
	struct cell *next;

	next = current->right;
	current->right = my_malloc(sizeof(struct cell));
	current->right->symbol = NULLCHR;
	current->right->left   = current;
	current->right->right  = next;
	if (next)
		next->left = current->right;

	return (current->right);
}

/*
 * This function takes a usual C-string, which represents the tape,
 * and initial index of head. It returns a "struct cell" pointer, which..
 * well, points to the specified cell of the tape.
 * The tape itself is represented as a doubly-linked list with blank-nodes
 * at both ends.
 */
static struct cell *
tape_init(char *data, const int head_position)
{
	char *lf;
	struct cell *ptr = NULL;
	register int i = 0;

	if ((lf = strrchr(data, '\n'))) *lf = '\0';

	ptr = my_malloc(sizeof(struct cell));
	ptr->symbol = 0;
	ptr->left   = NULL;
	ptr->right  = NULL;
	while (i < strlen(data)) {
		ptr = tape_insert_right(ptr);
		ptr->symbol = data[i];
		i++;
	}

	ptr = tape_insert_right(ptr);
	ptr->symbol = '\0';
	while (i > head_position && ptr->left) {
		ptr = ptr->left;
		i--;
	}

	return (ptr);
}

/*
 * This function basically frees a doubly-linked list.
 */
static int
tape_cleanup(struct cell *head)
{
	if (!head)
		return (1);
	while (head->left)
		head = head->left;
	while (head->right) {
		head = head->right;
		free(head->left);
	}
	free(head);
	return (0);
}

static void
tape_print(struct cell *head, bool with_cursor)
{
	struct cell *cursor = head;

	while (head && head->left)
		head = head->left;
	do {
		head = head->right;
		putchar(head->symbol);
	} while (head && head->right && head->right->right);
	putchar('\n');

	if (with_cursor) {
		while (cursor->left->left) {
			putchar(' ');
			cursor = cursor->left;
		}
		fputs("^\n", stdout);
	}
}

extern int
launch_tm(struct statepool *st_v, struct cell *head, bool verbose, bool changes,
		const int tolerance)
{
	struct state *st = st_v->states;
	register int opct = 0;

	if (verbose)
		printf("Starting Turing Machine...\n");
	st = find_rule(st_v, st_v->states[0].state_id, head->symbol);
	do {
		/* First, we need to find a rule that will be matching both
		 * current state and current symbol */
		/* Then we update the current symbol, move head (or don't)
		 * and switch to the next state as described in the current
		 * state */
		if (changes) tape_print(head, true);
		if (verbose) {
			printf("read  \'%c\'\nwrite \'%c\'\n",
				head->symbol, st->update_symbol);
			printf("state: %s, next state: %s\n",
					st->state_name, st->next_state_name);
		}
		head->symbol = st->update_symbol;
		if (head->left->symbol == '\0')
			tape_insert_left(head);
		if (head->right->symbol == '\0')
			tape_insert_right(head);

		switch (st->move) {
		case 'L': case 'l':
			if (verbose) puts("Move left");
			head = head->left;
			break;
		case 'R': case 'r':
			if (verbose) puts("Move right");
			head = head->right;
			break;
		case '.': case 'C': case 'c': case '-': case 'n': case 'N':
			if (verbose) puts("Head retains its position");
			break;
		}

		st = find_rule(st_v, st->next_state_id, head->symbol);
		opct++;
	} while (st && !st->is_final && opct < tolerance);

	if (st == NULL)
		puts("No matching next state found");
	if (verbose)
		puts("Turing machine terminated");
	if (opct >= tolerance)
		puts("Exceeded maximum number of operations");
	if (verbose || changes)
		printf("Operation count: %d\n", opct);

	tape_print(head, verbose || changes);
	return (0);
}

int
main(int argc, char **argv)
{
	char line[IN_BUF], *eol;
	struct statepool *v = NULL;
	struct cell *head = NULL;
	struct state sttmp;
	int head_position = 0;
	int ret = 0;
	bool verbose = false;
	bool changes = false;
	int tolerance = 100000;
	char state_name[ST_NAME_LEN],
		 next_state_name[ST_NAME_LEN];
	char **st_name_register = NULL;

	v = statepool_init();
	st_name_register = my_malloc(sizeof *st_name_register);
	st_name_register[0] = NULL;

	while (fgets(line, IN_BUF, stdin) &&
			strncmp(line, STR_FINAL_STATE, strlen(STR_FINAL_STATE))) {
		if (line[0] == '#' || !strncmp(line, "\n", 1))
			continue;
		if (sscanf(line, "%s %c -> %s %c %c",
					state_name, &sttmp.symbol,
					next_state_name, &sttmp.update_symbol, &sttmp.move) != 5) {
			printf("Failed to parse line \"%s\"\nTerminating\n", line);
			goto exit; 
			/* can you image the pain i'd have to go though to avoid this goto? */
		}
		sttmp.is_final = false;
		statenames_link(&st_name_register, &sttmp,
				state_name, next_state_name, v);
		statepool_append_copy(v, &sttmp);
	}
	statepool_sort(v, statecmp);
	(void) fgets(line, IN_BUF, stdin);
	mark_final_state(v, atoi(line));
	while (fgets(line, IN_BUF, stdin)) {
		/*
		 * Since we read the input file in this while loop,
		 * only the last occurrence of any settings statement is effective.
		 */

		/* skip comments */
		if (line[0] == '#' || line[0] == ';')
			continue;

		if (!strncmp(line, STR_HEAD_POSITION, strlen(STR_HEAD_POSITION))) {
			(void) fgets(line, IN_BUF, stdin);
			head_position = atoi(line);
		} else if (!strncmp(line, STR_TAPE, strlen(STR_TAPE))) {
			head = tape_init(fgets(line, IN_BUF, stdin), head_position);
		} else if (!strncmp(line, STR_VERBOSE, strlen(STR_VERBOSE))) {
			verbose = true;
		} else if (!strncmp(line, STR_CHANGES, strlen(STR_CHANGES))) {
			changes = true;
		} else if (!strncmp(line, STR_TOLLIM, strlen(STR_TOLLIM))) {
			(void) fgets(line, IN_BUF, stdin);
			if (sscanf(line, "%d\n", &tolerance) != 1) {
				fprintf(stderr, "Failed to read max. tolerance value, "
						"falling back to default (1e+5)\n");
				tolerance = 100000;
			}
		} else {
			if ((eol = strrchr(line, '\n')) != NULL)
				*eol = '\0';
			fprintf(stderr, "Failed to parse line \"%s\"\n", line);
			/* goto exit; */
		}
	}

	/* Start turing machine */
	ret |= launch_tm(v, head, verbose, changes, tolerance);

exit:
	ret |= st_name_register__free(&st_name_register);
	ret |= tape_cleanup(head);
	ret |= statepool_cleanup(v);
	return (ret);
}
